export const getInputs = () => [[3], [1]];

/**
 * [**22. 括号生成**](https://leetcode.cn/problems/generate-parentheses/)
 *
 * 数字 `n` 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 **有效的** 括号组合。
 *
 * 1. **示例 1：**
 * ```
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * ```
 *
 * 2. **示例 2：**
 * ```
 * 输入：n = 1
 * 输出：["()"]
 * ```
 *
 * @param n
 * @returns
 */
export default function (n: number): string[] {
	const result: string[] = [];

	/**
	 * 生成下一个括号
	 * @param generatedParenthesis 已生成的前缀括号字符串
	 * @param freeLeft 剩下的左括号数
	 * @param freeRight 剩下的有括号数
	 * @returns
	 */
	const generateNextParenthesis = (
		generatedParenthesis: string,
		freeLeft: number,
		freeRight: number
	) => {
		// 还存在可用的左括号，下一个符号还可能是左括号
		if (freeLeft !== 0) {
			generateNextParenthesis(`${generatedParenthesis}(`, freeLeft - 1, freeRight);
		}

		// 左右括号数目不一致，必然是左括号少于右括号，此时下一位可能是右括号
		if (freeLeft !== freeRight) {
			generateNextParenthesis(`${generatedParenthesis})`, freeLeft, freeRight - 1);
			return; // 数目不一致时终止函数运行
		}

		// 括号数目一致且为 0 ，添加至结果数组
		if (freeLeft === 0) result.push(generatedParenthesis);
	};

	generateNextParenthesis('', n, n);

	return result;
}
